Evidence grids are representations of terrain data obtained from sensors that measure characteristics of an environment. In at least one implementation, the sensors can acquire range and angle measurements of terrain features in the environment of the sensor. When the sensor is attached to a moving vehicle, evidence grids created at different times can provide navigational information that can be used to map the terrain and aid in providing a navigational solution for the vehicle. When evidence grids are used to provide navigational information, previously obtained data is combined to form a historical evidence grid, while recently obtained data is combined to form a current evidence grid. The historical evidence grid can be viewed as a compact view of the world that can be updated in real time. As such, the historical evidence grid is different from a fixed terrain map, such as the Digital Terrain Elevation Data (DTED), where DTED is a standard of digital datasets that includes a matrix of terrain elevation values. To determine the current position of a vehicle, a system correlates the current evidence grid with the historical evidence grid. The current evidence grid is adjusted through six degrees of freedom (three translational degrees of freedom along three perpendicular axes and three rotational degrees of freedom about the three perpendicular axes) to match the current evidence grid to the historical evidence grid. The adjustments can be processed to determine the movement of the vehicle since the historical evidence grid was created.
However, because both the current evidence grid and the historical evidence grid can also be used for path planning and obstacle avoidance (along with navigation), the evidence grids contain data describing empty space and the space inside objects in the environment, significantly increasing the amount of memory consumed by each evidence grid. For example, a single historical evidence grid can contain 5 million data points and use up to 120 MB of memory. The amount of data contained in evidence grids inhibits the ability of processors to correlate different evidence grids in a timely manner and may prevent evidence grids from being used for navigation in applications with faster time requirements.